package com.jxb.sort;

import java.util.Arrays;

/**
 * 最大堆排序-->实现增序
 * 实现原理：
 *  1：先将数据从非叶子节点int i = (len-1)/2构建成一个最大堆
 *      通过左子树(2*i + 1)和右子树(2(i+1))进行比较和交换，然后再进行递归
 *  2：循环将首位和末尾进行交换，再递归调整堆，将堆顶元素依次移除大小堆。
 *
 * 代码逻辑：
 *  1：首先进行堆的调整
 *  2：将堆的顶元素与尾元素互换，并进行堆的调整
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] nums = {1,3,5,3,9,4};
        sortArray(nums);
        System.out.println(nums);
    }

    //数组长度
    static int len;

    public static int[] sortArray(int[] nums) {
        if (nums.length <= 0) {
            return nums;
        }
        len = nums.length;
        //构建成一个最大堆
        buildMaxHeap(nums);
        //循环将堆首位和末尾数据进行交换,将堆顶元素依次移除大小堆
        while (len > 0) {
            swap(nums,0,len-1);
            len--;
            adjustHeap(nums,0);
        }
        return nums;
    }

    private static void buildMaxHeap(int[] nums) {
        //从最后一个非叶子节点开始向上构造最大堆
        for (int i = (len - 1)/2;i>=0;i--) {
            adjustHeap(nums, i);
        }
        System.out.println("构造完成最大堆");
        System.out.println(Arrays.toString(nums));
        System.out.println("============================================");
    }


    private static void adjustHeap(int[] nums, int i) {
        int maxIndex = i;//0->1
        int left = 2*i + 1;//63
        int right = 2*(i+1);//48

        //若有左子树，并且左子树大于父节点，则将最大指针指向父节点
        if (left < len && nums[left] > nums[maxIndex]) {
            maxIndex = left;
        }

        //若有右子树，并且右子树大于父节点并且大于左节点，则将最大指针指向右子树
        if (right < len && nums[right] > nums[maxIndex] && nums[right] > nums[left]) {
            maxIndex = right;
        }
        //若父节点不是最大值，将父节点与最大值交换，然后进行递归调整
        if (i != maxIndex) {
            //1,0
            swap(nums, maxIndex, i);
            adjustHeap(nums,maxIndex);
        }
    }

    private static void swap(int[] nums, int maxIndex, int i) {
        int temp = nums[maxIndex];
        nums[maxIndex] = nums[i];
        nums[i] = temp;
        System.out.println("经过一次调整的数组："+Arrays.toString(nums));
    }

}
